package com.dynasty;

import java.util.Random;

/**
 * @description Top N 问题：如何在10亿数据中找出前1000大的数
 * 其中数组默认不为空且大小大于0
 * 方法一：可以使用分治发(类似快排),时间复杂度o(n)
 * 方法二：小顶堆
 * Created by wangchao12 on 2019/4/27 0:24.
 */

public class TopN {
    /**
     * 方法的功能描述：父节点
     *
     * @param n
     * @return
     */
    private int parent(int n) {
        return (n - 1) / 2;
    }

    /**
     * 方法的功能描述：左孩子
     *
     * @param n
     * @return
     */
    private int left(int n) {
        return 2 * n + 1;
    }

    /**
     * 方法的功能描述：右孩子
     *
     * @param n
     * @return
     */
    private int rigth(int n) {
        return 2 * n + 2;
    }

    /**
     * 方法的功能描述：构建堆
     *
     * @param n
     * @return
     */
    private void buildHeap(int n, int[] data) {
        for (int i = 1; i < n; i++) {
            int t = i;
            /** 调整堆 **/
            while (t != 0 && data[parent(t)] > data[t]) {
                int temp = data[t];
                data[t] = data[parent(t)];
                data[parent(t)] = temp;
                t = parent(t);
            }
        }
    }

    /**
     * 方法的功能描述：调整data[i]
     *
     * @param i
     * @return
     */
    private void adjust(int i, int n, int[] data) {
        if (data[i] <= data[0]) {
            return;
        }
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
        /** 调整堆顶 **/
        int t = 0;
        while ((left(t) < n && data[t] > data[left(t)])
                || (rigth(t) < n && data[t] > data[rigth(t)])) {
            if (rigth(t) < n && data[rigth(t)] < data[left(t)]) {
                /** 右孩子更小，置换右孩子 **/
                temp = data[t];
                data[t] = data[rigth(t)];
                data[rigth(t)] = temp;
                t = rigth(t);
            } else {
                /** 否则置换左孩子 **/
                temp = data[t];
                data[t] = data[left(t)];
                data[left(t)] = temp;
                t = left(t);
            }
        }
    }

    /**
     * 方法的功能描述：调整data[i],该方法改变data,将topN排到最前面
     *
     * @param data
     * @return
     */
    private void findTopN(int n, int[] data) {
        /** 先构建n个数的小顶堆 **/
        buildHeap(n, data);
        /** n往后的数进行调整 **/
        int length = data.length;
        for (int i = n; i < length; i++) {
            adjust(i, n, data);
        }
    }

    /**
     * 方法的功能描述：打印数组
     *
     * @param data
     * @return
     */
    private void print(int[] data) {
        int length = data.length;
        for (int i = 0; i < length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        TopN topN = new TopN();

        /** 第一组测试 **/
        int[] data1 = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};
        System.out.println("原数组data1：");
        topN.print(data1);
        topN.findTopN(5, data1);
        System.out.println("调整后数组data1：");
        topN.print(data1);
        System.out.println();
        System.out.println();
        System.out.println();

        /** 第一组测试 **/
        int length = 1000;
        int[] data2 = new int[length];
        for (int i = 0; i < length; i++) {
            data2[i] = i + 1;
        }
        System.out.println("原数组data2：");
        topN.print(data2);
        topN.findTopN(50, data2);
        System.out.println("调整后数组data2：");
        topN.print(data2);
        System.out.println();
        System.out.println();
        System.out.println();

        /** 第一组测试 **/
        Random random = new Random();
        int[] data3 = new int[length];
        for (int i = 0; i < length; i++) {
            data3[i] = random.nextInt();
        }
        System.out.println("原数组data3：");
        topN.print(data3);
        topN.findTopN(50, data3);
        System.out.println("调整后数组data3：");
        topN.print(data3);
    }
}
